{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Days to Eat N Oranges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #吃掉 N 个橘子的最少天数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>厨房里总共有 <code>n</code>&nbsp;个橘子，你决定每一天选择如下方式之一吃这些橘子：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>吃掉一个橘子。</li>\n",
    "\t<li>如果剩余橘子数 <code>n</code>&nbsp;能被 2 整除，那么你可以吃掉 <code>n/2</code> 个橘子。</li>\n",
    "\t<li>如果剩余橘子数&nbsp;<code>n</code>&nbsp;能被 3 整除，那么你可以吃掉 <code>2*(n/3)</code> 个橘子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>每天你只能从以上 3 种方案中选择一种方案。</p>\n",
    "\n",
    "<p>请你返回吃掉所有 <code>n</code>&nbsp;个橘子的最少天数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 10\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>你总共有 10 个橘子。\n",
    "第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。\n",
    "第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除）\n",
    "第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。\n",
    "第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。\n",
    "你需要至少 4 天吃掉 10 个橘子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 6\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>你总共有 6 个橘子。\n",
    "第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除）\n",
    "第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除）\n",
    "第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。\n",
    "你至少需要 3 天吃掉 6 个橘子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 56\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2*10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-days-to-eat-n-oranges](https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-days-to-eat-n-oranges](https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10', '6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        uf = UnionFind(m*n)\n",
    "        cnt = 0\n",
    "        lst = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    for x, y in [[i+1, j], [i, j+1]]:\n",
    "                        if 0<=x<m and 0<=y<n and grid[x][y]:\n",
    "                            uf.union(i*n+j, x*n+y)\n",
    "                    cnt += 1\n",
    "                    lst.append([i, j])\n",
    "        if cnt <= 1:\n",
    "            return cnt\n",
    "        roots = [uf.find(i) for i in range(m*n) if grid[i//n][i%n]]\n",
    "        if len(set(roots)) > 1:\n",
    "            return 0\n",
    "        \n",
    "        for a, b in lst:\n",
    "            grid[a][b] = 0\n",
    "            \n",
    "            uf = UnionFind(m * n)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]:\n",
    "                        for x, y in [[i + 1, j], [i, j + 1]]:\n",
    "                            if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                                uf.union(i * n + j, x * n + y)\n",
    "            roots = [uf.find(i) for i in range(m * n) if grid[i // n][i % n]]\n",
    "            if len(set(roots)) > 1:\n",
    "                return 1\n",
    "            \n",
    "            grid[a][b] = 1\n",
    "        \n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        d=[[0,1],[1,0],[-1,0],[0,-1]]\n",
    "        def dfs(x,y,l):\n",
    "            if x<0 or x>=m or y<0 or y>=n:\n",
    "                return \n",
    "            if l[x][y]==0:\n",
    "                return \n",
    "            l[x][y]=0\n",
    "            for a,b in d:\n",
    "                dfs(x+a,y+b,l)\n",
    "        def isconnection():\n",
    "            g=copy.deepcopy(grid)\n",
    "            find=False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if g[i][j]==1:\n",
    "                        if find:\n",
    "                            return False\n",
    "                        find=True\n",
    "                        dfs(i,j,g)\n",
    "            if not find:\n",
    "                return False\n",
    "            return True\n",
    "        if not isconnection():\n",
    "            return 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    grid[i][j]=0\n",
    "                    #print(grid)\n",
    "                    if not isconnection():\n",
    "                        return 1\n",
    "                    grid[i][j]=1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x: int, y: int):\n",
    "            grid[x][y] = 2\n",
    "            for tx, ty in [(x, y + 1), (x + 1, y), (x, y - 1), (x - 1, y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx, ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "            # 还原\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        \n",
    "        # 岛屿数量不为 1，陆地已经分离\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        \n",
    "        return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x: int, y: int):\n",
    "            grid[x][y] = 2\n",
    "            for tx, ty in [(x, y + 1), (x + 1, y), (x, y - 1), (x - 1, y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx, ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "            # 还原\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        \n",
    "        # # 岛屿数量不为 1，陆地已经分离\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        \n",
    "        return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n, mn = len(grid), len(grid[0]), len(grid) * len(grid[0])\n",
    "        neighbors, degs = [[] for _ in range(mn)], [-1] * mn\n",
    "        steps = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    for step in steps:\n",
    "                        ii, jj = i + step[0], j + step[1]\n",
    "                        if ii >= 0 and ii < m and jj >= 0 and jj < n and grid[ii][jj] == 1:\n",
    "                            neighbors[i * n + j].append(ii * n + jj)\n",
    "                    degs[i * n + j] = len(neighbors[i * n +j])\n",
    "        def myCon():\n",
    "            parent, rank = list(range(mn)), [0] * mn\n",
    "            def myFind(x):\n",
    "                if x != parent[x]:\n",
    "                    parent[x] = myFind(parent[x])\n",
    "                return parent[x]\n",
    "            def myUnion(x, y):\n",
    "                px, py = myFind(x), myFind(y)\n",
    "                if px == py: return\n",
    "                if rank[px] > rank[py]:\n",
    "                    parent[py] = px\n",
    "                elif rank[px] < rank[py]:\n",
    "                    parent[px] = py\n",
    "                else:\n",
    "                    parent[py] = px\n",
    "                    rank[px] += 1\n",
    "                return\n",
    "            for i in range(mn):\n",
    "                if degs[i] > -1:\n",
    "                    for j in neighbors[i]:\n",
    "                        myUnion(i, j)\n",
    "            s = set()\n",
    "            for i in range(mn):\n",
    "                if degs[i] > -1:\n",
    "                    s.add(myFind(i))\n",
    "            return len(s) == 1\n",
    "        # Tarjan\n",
    "        def myCut():\n",
    "            dfn, low = [-1] * mn, [-1] * mn\n",
    "            time = [0]\n",
    "            for i in range(mn):\n",
    "                if degs[i] > 0:\n",
    "                    break\n",
    "            cut = set()\n",
    "            def dfs(x, fa):\n",
    "                dfn[x] = low[x] = time[0]\n",
    "                time[0] += 1\n",
    "                children = 0\n",
    "                for y in neighbors[x]:\n",
    "                    if y == fa: continue\n",
    "                    if dfn[y] != -1:\n",
    "                        low[x] = min(low[x], dfn[y])\n",
    "                    else:\n",
    "                        dfs(y, x)\n",
    "                        low[x] = min(low[x], low[y])\n",
    "                        children += 1\n",
    "                        if fa == -1 and children > 1:\n",
    "                            cut.add(x)\n",
    "                        if fa != -1 and low[y] >= dfn[x]:\n",
    "                            cut.add(x)\n",
    "                return\n",
    "            dfs(i, -1)\n",
    "            return len(cut) > 0\n",
    "\n",
    "        if not myCon():\n",
    "            return 0\n",
    "        if myCut():\n",
    "            return 1\n",
    "        else:\n",
    "            if degs.count(-1) == mn - 1:\n",
    "                return 1\n",
    "            else:\n",
    "                return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x: int, y: int):\n",
    "            grid[x][y] = 2\n",
    "            for tx, ty in [(x, y + 1), (x + 1, y), (x, y - 1), (x - 1, y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx, ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "            # 还原\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        \n",
    "        # 岛屿数量不为 1，陆地已经分离\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        \n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x:int, y:int):\n",
    "            grid[x][y] = 2\n",
    "            for tx,ty in [(x,y+1),(x+1,y),(x,y-1),(x-1,y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx,ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i,j)\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n , m = len(grid), len(grid[0])\n",
    "\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x:int, y:int):\n",
    "            grid[x][y] = 2\n",
    "            for tx,ty in [(x,y+1),(x+1,y),(x,y-1),(x-1,y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx,ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i,j)\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n , m = len(grid), len(grid[0])\n",
    "\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        def dfs(x, y):\n",
    "            for dx, dy in [[x + 1, y], [x - 1, y],[x, y - 1], [x, y + 1]]:\n",
    "                if 0 <= dx < m and 0 <= dy < n:\n",
    "                    if grid[dx][dy] == 1:\n",
    "                        grid[dx][dy] = 2\n",
    "                        dfs(dx, dy)\n",
    "        def check():\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "            \n",
    "        if check() != 1:\n",
    "            return 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    grid[i][j] = 0\n",
    "                    if check() != 1:\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x:int, y:int):\n",
    "            grid[x][y] = 2\n",
    "            for tx,ty in [(x,y+1),(x+1,y),(x,y-1),(x-1,y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx,ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i,j)\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n , m = len(grid), len(grid[0])\n",
    "\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = 2\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                    dfs(nx, ny)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        dfs(i, j)\n",
    "                        cnt += 1\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "            \n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    grid[i][j] = 2\n",
    "                    if count() != 1:\n",
    "                        return 1\n",
    "        return 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        def count(grid):\n",
    "            res = 0\n",
    "            used = [[0] * col for _ in range(row)]\n",
    "            for i in range(row):\n",
    "                for j in range(col):\n",
    "                    if grid[i][j] == 1 and used[i][j] == 0:\n",
    "                        used[i][j] = 1\n",
    "                        dfs(i, j, used)\n",
    "                        res += 1\n",
    "            return res\n",
    "        \n",
    "        def dfs(i, j, used):\n",
    "            for m, n in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:\n",
    "                if 0 <= m < row and 0 <= n < col and used[m][n] == 0 and grid[m][n] == 1:\n",
    "                    used[m][n] = 1\n",
    "                    dfs(m, n, used)\n",
    "            return\n",
    "        \n",
    "        island_num = count(grid)\n",
    "        if island_num != 1: return 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    grid[i][j] = 0\n",
    "                    island_num = count(grid)\n",
    "                    if island_num != 1: return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = 2\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                    dfs(nx, ny)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        dfs(i, j)\n",
    "                        cnt += 1\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "            \n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    grid[i][j] = 2\n",
    "                    if count() != 1:\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = 2\n",
    "\n",
    "            for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                if 0 <= nx <n and 0<=ny<m and grid[nx][ny] == 1:\n",
    "                    dfs(nx, ny)\n",
    "        m, n = len(grid[0]), len(grid)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "                        # print(grid)\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "\n",
    "            return cnt\n",
    "        # print(count())\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "\n",
    "        return 2 \n",
    "                \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        clk = 0 \n",
    "        def dfs(i, j):\n",
    "            nonlocal clk \n",
    "            clk += 1\n",
    "            vis[i][j] = 1\n",
    "            for [ni,nj] in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                if 0<=ni<m and 0<=nj<n and grid[ni][nj] == 1 and not vis[ni][nj]:\n",
    "                    dfs(ni,nj)\n",
    "            vis[i][j] = 2 \n",
    "            clk += 1 \n",
    "        comp = 0 \n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not vis[i][j]:\n",
    "                    dfs(i,j)\n",
    "                    comp+=1\n",
    "        if comp > 1:\n",
    "            return 0 \n",
    "        if clk // 2 <= 2:\n",
    "            return clk // 2 \n",
    "        \n",
    "        amt = clk // 2\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    vis = [[0] * n for _ in range(m)] \n",
    "                    grid[i][j] = 0 \n",
    "                    clk = 0\n",
    "                    for x in range(m):\n",
    "                        flag = 0\n",
    "                        for y in range(n):\n",
    "                            if grid[x][y] == 1:\n",
    "                                dfs(x, y)\n",
    "                                flag = 1\n",
    "                                break \n",
    "                        if flag:\n",
    "                            break \n",
    "                    #print(clk//2, amt, i, j)\n",
    "                    if clk // 2 < amt - 1:\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        tot = 0 \n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        clk = 0\n",
    "        def dfs(i, j):\n",
    "            nonlocal clk \n",
    "            vis[i][j] = 1\n",
    "            clk += 1 \n",
    "            for [ni,nj] in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                if 0<=ni<m and 0<=nj<n and grid[ni][nj] == 1:\n",
    "                    if not vis[ni][nj]:\n",
    "                        dfs(ni,nj) \n",
    "            vis[i][j] = 2\n",
    "            clk +=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not vis[i][j]:\n",
    "                    dfs(i, j) \n",
    "                    tot += 1\n",
    "        if tot == 0 or tot > 1:\n",
    "            return 0 \n",
    "        if clk // 2 == 2:\n",
    "            return 2\n",
    "        if clk // 2 == 1:\n",
    "            return 1 \n",
    "    \n",
    "        data = [i for i in range(n*m+1)]\n",
    "        def find(x):\n",
    "            if x == data[x]:\n",
    "                return x\n",
    "            else:\n",
    "                data[x] = find(data[x])\n",
    "                return data[x]\n",
    "        def un(x, y):\n",
    "            fx,fy = find(x),find(y)\n",
    "            if fx == fy:\n",
    "                return False \n",
    "            else:\n",
    "                data[fy] = fx\n",
    "                return True  \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    scnt = clk//2-1\n",
    "                    data = [i for i in range(n*m+1)]\n",
    "                    for x in range(m):\n",
    "                        for y in range(n):\n",
    "                            if grid[x][y] == 1 and (x,y)!= (i,j):\n",
    "                                for [nx,ny] in [[x+1,y],[x,y+1]]:\n",
    "                                    if 0<=nx<m and 0<=ny<n and grid[nx][ny] == 1 and (nx, ny) != (i, j):\n",
    "                                        if un(x*n+y, nx*n+ny):\n",
    "                                            scnt -= 1\n",
    "                            \n",
    "                    if scnt > 1:\n",
    "                        #print(scnt, i,j)\n",
    "                        return 1\n",
    "        return 2 \n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1] * n\n",
    "        self.comp_cnt = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def unite(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            if self.sz[x] < self.sz[y]:\n",
    "                x, y = y, x\n",
    "            self.fa[y] = x\n",
    "            self.sz[x] += self.sz[y]\n",
    "            self.comp_cnt -= 1\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        tot = m * n\n",
    "        uf = UF(tot)\n",
    "\n",
    "        mp = lambda t: t[0] * n + t[1]\n",
    "\n",
    "        zeros = 0\n",
    "        sr, sc = -1, -1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    zeros += 1\n",
    "                else:\n",
    "                    sr, sc = i, j\n",
    "                    for ni, nj in (i + 1, j), (i, j + 1):\n",
    "                        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                            uf.unite(mp((i, j)), mp((ni, nj)))\n",
    "\n",
    "        if uf.comp_cnt - zeros != 1: return 0 # no island or more than one island\n",
    "        if uf.comp_cnt == tot: return 1 # only one grid is 1\n",
    "\n",
    "        dfn = defaultdict(int)\n",
    "        low = defaultdict(int)\n",
    "        time = 1\n",
    "\n",
    "        def tarjan(x, y, fa):\n",
    "            nonlocal time\n",
    "            dfn[(x, y)] = low[(x, y)] = time\n",
    "            time += 1\n",
    "\n",
    "            cnt = 0\n",
    "            for dx, dy in pairwise([-1, 0, 1, 0, -1]):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and (nx, ny) != fa:\n",
    "                    if not dfn[(nx, ny)]:\n",
    "                        cnt += 1\n",
    "                        if tarjan(nx, ny, (x, y)): return True\n",
    "                        low[(x, y)] = min(low[(x, y)], low[(nx, ny)])\n",
    "                        if dfn[(x, y)] <= low[(nx, ny)]:\n",
    "                            if (x, y) != (sr, sc) or cnt > 1:\n",
    "                                return True\n",
    "                    else:\n",
    "                        low[(x, y)] = min(low[(x, y)], dfn[(nx, ny)])\n",
    "            return False\n",
    "        # tarjan(sr, sc, (-1, -1))\n",
    "        # print(dfn)\n",
    "        # print(low)\n",
    "        # print(sr, sc)\n",
    "        return 1 if tarjan(sr, sc, (-1, -1)) else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        new_map = copy.deepcopy(grid)\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        cnt = 0\n",
    "        \n",
    "        def dfs(i,j):\n",
    "            nonlocal cnt\n",
    "            cnt += 1\n",
    "            new_map[i][j] = 0\n",
    "            for di , dj in direction:\n",
    "                ni , nj = i + di , j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and new_map[ni][nj] == 1:\n",
    "                    dfs(ni,nj)\n",
    "\n",
    "        val = 0\n",
    "        start = None\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if new_map[i][j] == 1:\n",
    "                    val += 1\n",
    "                    dfs(i,j)\n",
    "                    if not start:\n",
    "                        start = (i,j)\n",
    "\n",
    "        if val > 1:\n",
    "            return 0\n",
    "        \n",
    "        if cnt <= 2:return cnt\n",
    "        low = defaultdict(int)\n",
    "        dfn = defaultdict(int)\n",
    "\n",
    "        def targan(node,parent,deep):\n",
    "\n",
    "            low[node] = dfn[node] = deep\n",
    "            i , j = node\n",
    "            x = 0\n",
    "            for di , dj in direction:\n",
    "                ni , nj = i + di , j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                    child = (ni,nj)\n",
    "                    if dfn[child] == 0:\n",
    "                        x += 1\n",
    "                        if targan(child,node,deep+1):\n",
    "                            return True\n",
    "                        low[node] = min(low[node],low[child])\n",
    "                        if dfn[node] <= low[child]:\n",
    "                            if x >= 2 or node != start:\n",
    "                                return True\n",
    "                    else:\n",
    "                        low[node] = min(low[node],dfn[child])\n",
    "            return False\n",
    "\n",
    "        if targan(start,None,1):\n",
    "            return 1\n",
    "        return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1] * n\n",
    "        self.comp_cnt = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def unite(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            if self.sz[x] < self.sz[y]:\n",
    "                x, y = y, x\n",
    "            self.fa[y] = x\n",
    "            self.sz[x] += self.sz[y]\n",
    "            self.comp_cnt -= 1\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        tot = m * n\n",
    "        uf = UF(tot)\n",
    "\n",
    "        mp = lambda t: t[0] * n + t[1]\n",
    "\n",
    "        zeros = 0\n",
    "        sr, sc = -1, -1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    zeros += 1\n",
    "                else:\n",
    "                    sr, sc = i, j\n",
    "                    for ni, nj in (i + 1, j), (i, j + 1):\n",
    "                        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                            uf.unite(mp((i, j)), mp((ni, nj)))\n",
    "\n",
    "        if uf.comp_cnt - zeros != 1: return 0 # no island or more than one island\n",
    "        if uf.comp_cnt == tot: return 1 # only one grid is 1\n",
    "\n",
    "        dfn = defaultdict(int)\n",
    "        low = defaultdict(int)\n",
    "        time = 1\n",
    "\n",
    "        def tarjan(x, y, fa):\n",
    "            nonlocal time\n",
    "            dfn[(x, y)] = low[(x, y)] = time\n",
    "            time += 1\n",
    "\n",
    "            cnt = 0\n",
    "            for dx, dy in pairwise([-1, 0, 1, 0, -1]):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and (nx, ny) != fa:\n",
    "                    if not dfn[(nx, ny)]:\n",
    "                        cnt += 1\n",
    "                        if tarjan(nx, ny, (x, y)): return True\n",
    "                        low[(x, y)] = min(low[(x, y)], low[(nx, ny)])\n",
    "                        if dfn[(x, y)] <= low[(nx, ny)]:\n",
    "                            if (x, y) != (sr, sc) or cnt > 1:\n",
    "                                return True\n",
    "                    else:\n",
    "                        low[(x, y)] = min(low[(x, y)], dfn[(nx, ny)])\n",
    "            return False\n",
    "        return 1 if tarjan(sr, sc, (-1, -1)) else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        graph = collections.defaultdict(list)\n",
    "        parent = {i : i for i in range(m * n)}\n",
    "        size = [1] * (m * n)\n",
    "        self.size = 0\n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node \n",
    "            return node \n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                parent[p1] = p2 \n",
    "                size[p2] += size[p1]\n",
    "                self.size -= 1 \n",
    "        \n",
    "        def neigh(i, j):\n",
    "            for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                    yield x, y \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    continue \n",
    "                self.size += 1 \n",
    "                for x, y in neigh(i, j):\n",
    "                    union(x * n + y, i * n + j)\n",
    "                    graph[i * n + j].append(x * n + y)\n",
    "                    # graph[x * n + y].append(i * n + j)\n",
    "        \n",
    "        dfn = [-1] * (m * n)\n",
    "        low = [-1] * (m * n)\n",
    "        self.found = False \n",
    "        def tarjan(node, time, par):\n",
    "            dfn[node] = time \n",
    "            low[node] = time \n",
    "            child = 0\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                if dfn[nei] == - 1:\n",
    "                    tarjan(nei, time + 1, node)\n",
    "                    child += 1 \n",
    "                    if (par == - 1 and child > 1) or (par != - 1 and low[nei] >= dfn[node]):\n",
    "                        self.found = True \n",
    "                    low[node] = min(low[node], low[nei])\n",
    "                else:\n",
    "                    low[node] = min(low[node], dfn[nei])\n",
    "        \n",
    "\n",
    "        if self.size != 1:\n",
    "            return 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if size[find(i * n + j)] == 1:\n",
    "                        return 1 \n",
    "                    tarjan(i * n + j, 0, - 1)\n",
    "                    if self.found:\n",
    "                        return 1 \n",
    "                    break\n",
    "        return 2 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        H,W = len(grid),len(grid[0])\n",
    "        g = collections.defaultdict(list)\n",
    "        \n",
    "        cnt = 0\n",
    "        visited = [False]*(H*W)\n",
    "        DIRs = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "        def to1d(i,j):\n",
    "            return i*W+j\n",
    "\n",
    "        def dfs(i,j):\n",
    "            visited[to1d(i,j)] = True\n",
    "            for di,dj in DIRs:\n",
    "                ni,nj = i+di,j+dj\n",
    "                if 0<=ni<H and 0<=nj<W and grid[ni][nj]==1:\n",
    "                    g[to1d(i,j)].append(to1d(ni,nj))\n",
    "                    if not visited[to1d(ni,nj)]:\n",
    "                        dfs(ni,nj)\n",
    "        \n",
    "        for i,row in enumerate(grid):\n",
    "            for j,n in enumerate(row):\n",
    "                if n == 1 and not visited[to1d(i,j)]:\n",
    "                    cnt += 1\n",
    "                    dfs(i,j)\n",
    "\n",
    "        if cnt!=1: return 0\n",
    "        if not g: return 1\n",
    "        # find articulation point - tarjan's algorithm\n",
    "        # only one connected component\n",
    "        def tarjan(graph):\n",
    "            arti = set() # articulation points\n",
    "            _id = 0\n",
    "            ids = collections.defaultdict(lambda: -1)\n",
    "            lows = collections.defaultdict(lambda: -1)\n",
    "            out = 0\n",
    "\n",
    "            def dfs(i, root, parent):\n",
    "                nonlocal _id, out\n",
    "                ids[i] = lows[i] = _id\n",
    "                _id += 1\n",
    "                out += int(parent==root)\n",
    "\n",
    "                for nei in graph[i]:\n",
    "                    if nei == parent: continue\n",
    "                    if ids[nei] == -1:\n",
    "                        dfs(nei, root, i)\n",
    "                        lows[i] = min(lows[i], lows[nei])\n",
    "                        if ids[i] <= lows[nei]:\n",
    "                            arti.add(i)\n",
    "                    else:\n",
    "                        lows[i] = min(lows[i], ids[nei])\n",
    "\n",
    "\n",
    "            for i in graph.keys():\n",
    "                if ids[i] == -1:\n",
    "                    out = 0\n",
    "                    dfs(i, i, -1)\n",
    "                    if i in arti and out<=1:\n",
    "                        arti.remove(i)\n",
    "\n",
    "            return arti\n",
    "\n",
    "\n",
    "        return 1 if tarjan(g) else 2\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        graph = collections.defaultdict(list)\n",
    "        parent = {i : i for i in range(m * n)}\n",
    "        size = [1] * (m * n)\n",
    "        self.size = 0\n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node \n",
    "            return node \n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                parent[p1] = p2 \n",
    "                size[p2] += size[p1]\n",
    "                self.size -= 1 \n",
    "        \n",
    "        def neigh(i, j):\n",
    "            for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                    yield x, y \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    continue \n",
    "                self.size += 1 \n",
    "                for x, y in neigh(i, j):\n",
    "                    union(x * n + y, i * n + j)\n",
    "                    graph[i * n + j].append(x * n + y)\n",
    "                    # graph[x * n + y].append(i * n + j)\n",
    "        \n",
    "        dfn = [-1] * (m * n)\n",
    "        low = [-1] * (m * n)\n",
    "        self.found = False \n",
    "        def tarjan(node, time, par):\n",
    "            dfn[node] = time \n",
    "            low[node] = time \n",
    "            child = 0\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                if dfn[nei] == - 1:\n",
    "                    tarjan(nei, time + 1, node)\n",
    "                    child += 1 \n",
    "                    if (par == - 1 and child > 1) or (par != - 1 and low[nei] >= dfn[node]):\n",
    "                        self.found = True \n",
    "                    low[node] = min(low[node], low[nei])\n",
    "                else:\n",
    "                    low[node] = min(low[node], dfn[nei])\n",
    "        \n",
    "\n",
    "        if self.size != 1:\n",
    "            return 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if size[find(i * n + j)] == 1:\n",
    "                        return 1 \n",
    "                    tarjan(i * n + j, 0, - 1)\n",
    "                    if self.found:\n",
    "                        return 1 \n",
    "                    break\n",
    "        return 2 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        return min(n % 2 + 1 + self.minDays(n // 2), n % 3 + 1 + self.minDays(n // 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        res_list = [n]\n",
    "        history = []\n",
    "        res = n\n",
    "\n",
    "        cnt = [0]\n",
    "        cur = 0\n",
    "        while res != 0:\n",
    "            res = res_list.pop(0)\n",
    "            cur = cnt.pop(0)\n",
    "            if res-1 not in history:\n",
    "                res_list.append(res-1)\n",
    "                cnt.append(cur+1)\n",
    "                history.append(res-1)\n",
    "            if res%2 == 0 and res/2 not in history:\n",
    "                res_list.append(res/2)\n",
    "                cnt.append(cur+1)\n",
    "                history.append(res/2)\n",
    "            if res%3 == 0 and res/3 not in history:\n",
    "                res_list.append(res/3)\n",
    "                cnt.append(cur+1)\n",
    "                history.append(res/3)\n",
    "\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        res_list = [n]\n",
    "        history = []\n",
    "        res = n\n",
    "\n",
    "        cnt = [0]\n",
    "        cur = 0\n",
    "        while res != 0:\n",
    "            res = res_list.pop(0)\n",
    "            cur = cnt.pop(0)\n",
    "            if res-1 not in history:\n",
    "                res_list.append(res-1)\n",
    "                cnt.append(cur+1)\n",
    "                history.append(res-1)\n",
    "            if res%2 == 0 and res/2 not in history:\n",
    "                res_list.append(res/2)\n",
    "                cnt.append(cur+1)\n",
    "                history.append(res/2)\n",
    "            if res%3 == 0 and res/3 not in history:\n",
    "                res_list.append(res/3)\n",
    "                cnt.append(cur+1)\n",
    "                history.append(res/3)\n",
    "\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        res_list = [n]\n",
    "        history = set()\n",
    "        res = n\n",
    "\n",
    "        cnt = [0]\n",
    "        cur = 0\n",
    "        while res != 0:\n",
    "            res = res_list.pop(0)\n",
    "            cur = cnt.pop(0)\n",
    "            if res-1 not in history:\n",
    "                res_list.append(res-1)\n",
    "                cnt.append(cur+1)\n",
    "                history.add(res-1)\n",
    "            if res%2 == 0 and res/2 not in history:\n",
    "                res_list.append(res/2)\n",
    "                cnt.append(cur+1)\n",
    "                history.add(res/2)\n",
    "            if res%3 == 0 and res/3 not in history:\n",
    "                res_list.append(res/3)\n",
    "                cnt.append(cur+1)\n",
    "                history.add(res/3)\n",
    "\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def getHeuristicValue(rest: float) -> int:\n",
    "            return 0 if rest == 0 else \\\n",
    "                int(math.log(rest) / math.log(3.0)) + 1\n",
    "        \n",
    "        q = [(getHeuristicValue(n), 0, n)]\n",
    "        visited = set()\n",
    "        ans = 0\n",
    "        \n",
    "        while True:\n",
    "            expected, days, rest = heapq.heappop(q)\n",
    "            if rest in visited:\n",
    "                continue\n",
    "            visited.add(rest)\n",
    "            if rest == 1:\n",
    "                ans = days + 1\n",
    "                break\n",
    "            heapq.heappush(q, (\n",
    "                days + rest % 2 + 1 + getHeuristicValue(rest // 2),\n",
    "                days + rest % 2 + 1,\n",
    "                rest // 2\n",
    "            ))\n",
    "            heapq.heappush(q, (\n",
    "                days + rest % 3 + 1 + getHeuristicValue(rest // 3),\n",
    "                days + rest % 3 + 1,\n",
    "                rest // 3\n",
    "            ))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        d = deque([(n,0)])\n",
    "        st = set()\n",
    "        while d:\n",
    "            c, h = d.popleft()\n",
    "            if not c:\n",
    "                return h\n",
    "            if c in st:\n",
    "                continue\n",
    "            st.add(c)\n",
    "            d.append([c-1, h+1])\n",
    "            if c%2 == 0:\n",
    "                d.append([c//2, h+1])\n",
    "            if c%3 == 0:\n",
    "                d.append([c//3, h+1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        st=[]\n",
    "        heapq.heappush(st,(0,n))\n",
    "        seen=set()\n",
    "        while heapq :\n",
    "            dep,m=heapq.heappop(st)\n",
    "            if m in seen:continue\n",
    "            seen.add(m)\n",
    "            if m==0:return dep\n",
    "            div2,mod2=divmod(m,2)\n",
    "            div3,mod3=divmod(m,3)\n",
    "            if not mod2:\n",
    "                heapq.heappush(st,(dep+1,div2))\n",
    "            else:\n",
    "                heapq.heappush(st,(dep+mod2,m-mod2))\n",
    "            if not mod3:\n",
    "                heapq.heappush(st,(dep+1,div3))\n",
    "            else:\n",
    "                heapq.heappush(st,(dep+mod3,m-mod3))\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        res_list = [n]\n",
    "        history = []\n",
    "        res = n\n",
    "\n",
    "        cnt = [0]\n",
    "        cur = 0\n",
    "        while res != 0:\n",
    "            res = res_list.pop(0)\n",
    "            cur = cnt.pop(0)\n",
    "            if res-1 not in history:\n",
    "                res_list.append(res-1)\n",
    "                cnt.append(cur+1)\n",
    "                history.append(res-1)\n",
    "            if res%2 == 0 and res/2 not in history:\n",
    "                res_list.append(res/2)\n",
    "                cnt.append(cur+1)\n",
    "                history.append(res/2)\n",
    "            if res%3 == 0 and res/3 not in history:\n",
    "                res_list.append(res/3)\n",
    "                cnt.append(cur+1)\n",
    "                history.append(res/3)\n",
    "\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        # 广度搜索\n",
    "        q = deque([[n,0]]) # 剩余个数，天数\n",
    "        visited = set()\n",
    "        while q:\n",
    "            curN, cost = q.popleft()\n",
    "            if curN == 0:\n",
    "                return cost\n",
    "            if curN in visited:\n",
    "                continue\n",
    "            q.append([curN-1, cost+1])\n",
    "            if curN % 2 == 0:\n",
    "                q.append([curN//2, cost+1])\n",
    "            if curN % 3 == 0:\n",
    "                q.append([curN//3, cost+1])\n",
    "            visited.add(curN)\n",
    "    def minDays1(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(curN):\n",
    "            if curN == 0:\n",
    "                return 0\n",
    "            if curN == 1:\n",
    "                return 1\n",
    "            return 1 + min(dfs(curN//2) + curN % 2, dfs(curN//3) + curN % 3)\n",
    "        return dfs(n)\n",
    "    def minDays2(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(curN):\n",
    "            if curN < 0:\n",
    "                return float(\"inf\")\n",
    "            if curN == 0:\n",
    "                return 0\n",
    "            ans = float(\"inf\")\n",
    "            # 能被2整除\n",
    "            if curN % 2 == 0:\n",
    "                ans = min(ans, dfs(curN // 2) + 1)\n",
    "            if curN % 3 == 0:\n",
    "                ans = min(ans, dfs(curN // 3) + 1)\n",
    "            # 吃一个\n",
    "            ans = min(ans, dfs(curN - 1) + 1)\n",
    "            return ans\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        res_list = [n]\n",
    "        history = set()\n",
    "        res = n\n",
    "\n",
    "        cnt = [0]\n",
    "        cur = 0\n",
    "        while res != 0:\n",
    "            res = res_list.pop(0)\n",
    "            cur = cnt.pop(0)\n",
    "            if res-1 not in history:\n",
    "                res_list.append(res-1)\n",
    "                cnt.append(cur+1)\n",
    "                history.add(res-1)\n",
    "            if res%2 == 0 and res/2 not in history:\n",
    "                res_list.append(res/2)\n",
    "                cnt.append(cur+1)\n",
    "                history.add(res/2)\n",
    "            if res%3 == 0 and res/3 not in history:\n",
    "                res_list.append(res/3)\n",
    "                cnt.append(cur+1)\n",
    "                history.add(res/3)\n",
    "\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        res_list = [n]\n",
    "        history = set()\n",
    "        res = n\n",
    "\n",
    "        cnt = [0]\n",
    "        cur = 0\n",
    "        while res != 0:\n",
    "            res = res_list.pop(0)\n",
    "            cur = cnt.pop(0)\n",
    "            if res-1 not in history:\n",
    "                res_list.append(res-1)\n",
    "                cnt.append(cur+1)\n",
    "                history.add(res-1)\n",
    "            if res%2 == 0 and res/2 not in history:\n",
    "                res_list.append(res/2)\n",
    "                cnt.append(cur+1)\n",
    "                history.add(res/2)\n",
    "            if res%3 == 0 and res/3 not in history:\n",
    "                res_list.append(res/3)\n",
    "                cnt.append(cur+1)\n",
    "                history.add(res/3)\n",
    "\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        queue = collections.deque([(n, 0)])\n",
    "        seen = set()\n",
    "        seen.add(n)\n",
    "        while queue:\n",
    "            node, step = queue.popleft()\n",
    "            if node == 0:\n",
    "                return step\n",
    "            if node - 1 not in seen:\n",
    "                queue.append((node - 1, step + 1))\n",
    "                seen.add(node - 1)\n",
    "            \n",
    "            if node % 2 == 0 and node// 2 not in seen:\n",
    "                queue.append((node // 2, step + 1))\n",
    "                seen.add(node // 2)\n",
    "\n",
    "            if node % 3 == 0 and node // 3 not in seen:\n",
    "                queue.append((node // 3, step + 1))\n",
    "                seen.add(node // 3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        dp, has, k = {n}, {n}, 1\n",
    "        while 1 not in has:\n",
    "            ndp = set()\n",
    "            for i in dp:\n",
    "                if i-1 not in has:\n",
    "                    ndp.add(i-1)\n",
    "                    has.add(i-1)\n",
    "                if i%2==0 and i//2 not in has:\n",
    "                    ndp.add(i//2)\n",
    "                    has.add(i//2)\n",
    "                if i%3==0 and i//3 not in has:\n",
    "                    ndp.add(i//3)\n",
    "                    has.add(i//3)\n",
    "            k, dp = k + 1, ndp\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minDays(self, n: int) -> int:\n",
    "#         memo = {}\n",
    "#         def dfs(n):\n",
    "#             if n in memo:\n",
    "#                 return memo[n]\n",
    "#             if n <= 0:\n",
    "#                 return 0\n",
    "#             res = float('inf')         \n",
    "#             if n % 2 == 0:\n",
    "#                 res  = min(res, dfs(n - n//2) + 1)\n",
    "#             if n % 3 == 0:\n",
    "#                 res = min(res, dfs(n -2*(n//3)) + 1)\n",
    "#             if n % 2 != 0 or n % 3 != 0: # muust have or MLE\n",
    "#                 res = min(res, dfs(n-1) +1)\n",
    "#             memo[n] = res\n",
    "#             return res\n",
    "#         return dfs(n)\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "memorization - O(logN)\n",
    "这类题的首选算法是BFS, 因为BFS只需要闭着眼睛一步一步往前就可以了。\n",
    "而backtrack + memo的方法需要贪心判断不能除2或除3才能进行-1的操作！否则会导致算法degrade to O(N) TLE. 这里是很容易出错的！\n",
    "\"\"\"\n",
    "\"\"\"\n",
    "bfs: O(logN) because each step we on average can get rid of n/2 nodes.\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        queue = collections.deque()\n",
    "        visited = set()\n",
    "        queue.append([n, 0])\n",
    "        visited.add(n)\n",
    "        \n",
    "        while queue:\n",
    "            curr_num, step = queue.popleft()\n",
    "            if curr_num <= 0:\n",
    "                return step\n",
    "            # Eat one orange.\n",
    "            if curr_num - 1 not in visited:\n",
    "                queue.append([curr_num - 1, step + 1])\n",
    "                visited.add(curr_num - 1)\n",
    "            # If the number of remaining oranges n is divisible by 2 then you can eat n / 2 oranges.\n",
    "            if curr_num % 2 == 0 and curr_num // 2 not in visited:\n",
    "                queue.append([curr_num // 2, step + 1])\n",
    "                visited.add(curr_num // 2)\n",
    "            # If the number of remaining oranges n is divisible by 3 then you can eat 2 * (n / 3) oranges.\n",
    "            if curr_num % 3 == 0 and curr_num // 3 not in visited:\n",
    "                queue.append([curr_num // 3, step + 1])\n",
    "                visited.add((curr_num // 3))\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        dic = defaultdict(lambda:inf)\n",
    "        dic[n] = 0\n",
    "        for _ in range(n):\n",
    "            keys = list(dic.keys())\n",
    "            for k in keys:\n",
    "                if k%2 == 0:\n",
    "                    dic[k//2] = min(dic[k//2],dic[k]+1)\n",
    "                if k%3 == 0:\n",
    "                    dic[k//3] = min(dic[k//3],dic[k]+1)\n",
    "                dic[k-1] = min(dic[k-1],dic[k]+1)\n",
    "            #print(dic.items())\n",
    "            if 0 in dic.keys():\n",
    "                return dic[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(x:int):\n",
    "            if x == 1:\n",
    "                return 1\n",
    "            if x <= 0:\n",
    "                return 0\n",
    "            r = inf\n",
    "            r = min(r, f(x // 2) + x % 2 + 1)\n",
    "            r = min(r, f(x // 3) + x % 3 + 1)\n",
    "            return r\n",
    "       \n",
    "        return  f(n)\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "\n",
    "        hashmap = dict()\n",
    "        \n",
    "        def A(n):\n",
    "            if n <= 1:\n",
    "                return n\n",
    "            if n in hashmap:\n",
    "                return hashmap[n]\n",
    "            res = min(n % 2 + 1 + A(n // 2), n % 3 + 1 + A(n // 3))\n",
    "            hashmap[n] = res\n",
    "            return res\n",
    "\n",
    "        return A(n)\n",
    "                \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "memo: dict[int, int] = dict()\r\n",
    "class Solution:\r\n",
    "    def minDays(self, n: int) -> int:\r\n",
    "        if n < 2: return n\r\n",
    "        if n not in memo:\r\n",
    "            memo[n] = min(self.minDays(n // 2) + n % 2, self.minDays(n // 3) + n % 3) + 1\r\n",
    "        return memo[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(left):\n",
    "            # print(left)\n",
    "            if left <= 1:\n",
    "                return left\n",
    "            # if left % 3 == 0:\n",
    "            #     return 1 + dfs(left // 3)\n",
    "            return min(left % 3 + dfs(left // 3), left % 2 + dfs(left // 2)) + 1\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0 or i == 1 or i == 2: return i\n",
    "            ans = min(dfs(i//3) + dfs(i%3) + 1, dfs(i//2) + dfs(i%2) + 1)\n",
    "            return ans\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == 0:\n",
    "                return -1\n",
    "            return 1 + min(f(i//2) + i % 2, f(i//3) + i % 3)\n",
    "\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def f(cur):\n",
    "            if not cur:\n",
    "                return 0\n",
    "            elif cur == 1:\n",
    "                return 1\n",
    "            a, b = divmod(cur, 2)\n",
    "            c, d = divmod(cur, 3)\n",
    "            res1 = f(a) + b + 1\n",
    "            res2 = f(c) + d + 1\n",
    "            return min(res1, res2)\n",
    "\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(x):\n",
    "\n",
    "            if x == 1:\n",
    "                return 1\n",
    "\n",
    "            if x%2 == 0:\n",
    "                res = 1 + f(x//2)\n",
    "            else:\n",
    "                res = 2 + f(x//2)\n",
    "\n",
    "            if x%3 == 0:\n",
    "                res = min(res, 1 + f(x//3))\n",
    "            elif x%3 == 1 and x>3:\n",
    "                res = min(res, 2+f(x//3))\n",
    "            elif x>3:\n",
    "                res = min(res, 3+f(x//3))\n",
    "            return res\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        dp={}\n",
    "        dp[0]=0;dp[1]=1;dp[2]=2\n",
    "        # 用字典存储了到n的最小值，类似cache\n",
    "        def dfs(n):\n",
    "            if n in dp: return dp[n]\n",
    "            three=n%3+(1+dfs(n//3))\n",
    "            two=n%2+(1+dfs(n//2))\n",
    "            dp[n]=min(two,three)\n",
    "            return dp[n]\n",
    "        return dfs(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        # 2 3 4 5 6 7 8 9 10\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n < 2:\n",
    "                return n\n",
    "            return 1 + min(dfs(n//2) + n % 2,dfs(n // 3) + n % 3)\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(n: int) -> int:\n",
    "            if n<=1:\n",
    "                return n\n",
    "            return min(n%3+1+dfs(n//3),n%2+1+dfs(n//2))\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(x: int) -> int:\n",
    "            if x <= 1: return x\n",
    "            return min(1 + x % 2 + dfs(x // 2), 1 + x % 3 + dfs(x // 3))\n",
    "        return dfs(n)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "\n",
    "        hashmap = dict()\n",
    "        @lru_cache(None)\n",
    "        def A(n):\n",
    "            if n <= 1:\n",
    "                return n\n",
    "            \n",
    "            res = min(n % 2 + 1 + A(n // 2), n % 3 + 1 + A(n // 3))\n",
    "            \n",
    "            return res\n",
    "\n",
    "        return A(n)\n",
    "                \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "\n",
    "       \n",
    "        @lru_cache(None)\n",
    "        def A(n):\n",
    "            if n <= 1:\n",
    "                return n\n",
    "            \n",
    "            res = min(n % 2 + 1 + A(n // 2), n % 3 + 1 + A(n // 3))\n",
    "            \n",
    "            return res\n",
    "\n",
    "        return A(n)\n",
    "                \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(x):\n",
    "\n",
    "            if x <= 1:\n",
    "                return x\n",
    "\n",
    "            if x%2 == 0:\n",
    "                res = 1 + f(x//2)\n",
    "            else:\n",
    "                res = 2 + f(x//2)\n",
    "\n",
    "            if x%3 == 0:\n",
    "                res = min(res, 1 + f(x//3))\n",
    "            elif x%3 == 1 :\n",
    "                res = min(res, 2+f(x//3))\n",
    "            else:\n",
    "                res = min(res, 3+f(x//3))\n",
    "            return res\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        # def lt1553(n):\n",
    "        #     mem=defaultdict(int)\n",
    "        #     mem[1],mem[2],mem[3],mem[4]=1,2,2,3\n",
    "        #     def dfs(n):\n",
    "        #         if not mem[n]:\n",
    "        #             if n%2==0 or n%3==0:\n",
    "        #                 temp=[]\n",
    "        #                 if n%2==0:temp.append(1+dfs(n//2))\n",
    "        #                 if n%3==0:temp.append(1+dfs(n//3))\n",
    "        #                 mem[n] = min(temp)\n",
    "        #             else:mem[n]=dfs(n-1)+1\n",
    "        #         return mem[n]\n",
    "        #     return dfs(n)\n",
    "        # return lt1553(n)\n",
    "\n",
    "        #     if n==1:return 1\n",
    "        #     if n==2 or n==3:return 2\n",
    "        #     if n==4:return 3\n",
    "        #     c=[0]*(n+1)\n",
    "        #     c[1],c[2],c[3],c[4]=1,2,2,3\n",
    "        #     for i in range(5,n+1):\n",
    "        #         temp=[c[i-1]]\n",
    "        #         if i%2==0:temp.append(c[i//2])\n",
    "        #         if i%3==0:temp.append(c[i//3])\n",
    "        #         c[i]=min(temp)+1\n",
    "        #     return c[-1]\n",
    "        # return lt1553(n)\n",
    "\n",
    "        def lt1553(n):\n",
    "            mem=defaultdict(int)\n",
    "            mem[1],mem[2],mem[3],mem[4]=1,2,2,3\n",
    "            def dfs(n):\n",
    "                if not mem[n]:\n",
    "                    temp=[]\n",
    "                    temp.append(n%2+1+dfs(n//2))\n",
    "                    temp.append(n%3+1+dfs(n//3))\n",
    "                    mem[n]=min(temp)\n",
    "                return mem[n]\n",
    "            return dfs(n)\n",
    "        return lt1553(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(left):\n",
    "            if left <= 1:\n",
    "                return left\n",
    "            return min(left % 2 + 1 + dfs(left // 2), left % 3 + 1 + dfs(left // 3))\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n < 2:\n",
    "                return n\n",
    "            return 1 + min(dfs(n//2) + n % 2,dfs(n // 3) + n % 3)\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        visited = {}\n",
    "        if n<=1:\n",
    "                return n \n",
    "        def search(n):\n",
    "            nonlocal visited \n",
    "            if n in visited:\n",
    "                return visited[n]\n",
    "            if n<=1:\n",
    "                return n \n",
    "            branch1 = n # 一个个吃\n",
    "            branch2 = search(n//2)+ n%2 + 1 # 一个个吃到2的整数倍\n",
    "            branch3 = search(n//3)+ n%3 + 1 # 一个个吃到3的整数倍\n",
    "            visited[n] = min(branch1,branch2,branch3)\n",
    "            return visited[n]\n",
    "        return search(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0 or i == 1 or i == 2: return i\n",
    "            return  min(dfs(i//3) + dfs(i%3) + 1, dfs(i//2) + dfs(i%2) + 1)\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(x: int) -> int:\n",
    "            if x == 1:\n",
    "                return 1\n",
    "            if x == 2:\n",
    "                return 2\n",
    "            if x == 3:\n",
    "                return 2\n",
    "            return min(dfs(x // 3) + x % 3, dfs(x // 2) + x % 2) + 1\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        dp={}\n",
    "        dp[0]=0;dp[1]=1;dp[2]=2\n",
    "        def dfs(n):\n",
    "            if n in dp: return dp[n]\n",
    "            three=n%3+(1+dfs(n//3))\n",
    "            two=n%2+(1+dfs(n//2))\n",
    "            dp[n]=min(two,three)\n",
    "            return dp[n]\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(x):\n",
    "\n",
    "            if x <= 1:\n",
    "                return x\n",
    "            return min(x%2+1 + f(x//2), x%3+1 + f(x//3))\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(x):\n",
    "            if x==1:\n",
    "                return 1 \n",
    "            elif x==2:\n",
    "                return 2 \n",
    "            elif x==3:\n",
    "                return 2 \n",
    "            else:\n",
    "                return min(f(x//2) + x%2, f(x//3) + x%3) + 1\n",
    "        return f(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def recur(n):\n",
    "            if n <= 1:\n",
    "                return n\n",
    "            res = inf\n",
    "            res = min(res,n%3 + recur(n//3) + 1)\n",
    "            res = min(res,n%2 + recur(n//2) + 1)\n",
    "            return res\n",
    "        return recur(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(x:int):\n",
    "            if x <= 0:\n",
    "                return 0\n",
    "            r = inf\n",
    "            r = min(r, f(x // 2) + x % 2 + 1)\n",
    "            r = min(r, f(x // 3) + x % 3 + 1)\n",
    "            return r\n",
    "            \n",
    "           \n",
    "       \n",
    "        return  f(n) - 1\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x == 1:\n",
    "                return 1 \n",
    "            if x == 0:\n",
    "                return 0\n",
    "            res = inf\n",
    "            if x % 2 == 0:\n",
    "                res = min(res, dfs(x//2) + 1)\n",
    "            if x % 3 == 0:\n",
    "                res = min(res, dfs(x//3) + 1)\n",
    "            if (x-1) % 2 == 0:\n",
    "                res = min(res, dfs((x-1)//2) + 2)\n",
    "            if (x-1) % 3 == 0:\n",
    "                res = min(res, dfs((x-1)//3) + 2)\n",
    "            if (x-2) % 3 == 0:\n",
    "                res = min(res, dfs((x-2)//3) + 3)\n",
    "\n",
    "            return res \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(tot):\n",
    "            if tot <= 1:\n",
    "                return tot\n",
    "            return min(dfs(tot // 3) + tot % 3 + 1, dfs(tot // 2) + tot % 2 + 1)\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(num):\n",
    "            print(num)\n",
    "            if num <= 1: return num\n",
    "            return min(num % 2 + 1 + dfs(num // 2), num % 3 + 1 + dfs(num // 3))\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(n):\n",
    "            if n==1:\n",
    "                return 1\n",
    "            elif n==2:\n",
    "                return 2\n",
    "            elif n==3:\n",
    "                return 2\n",
    "            elif n==4:\n",
    "                return 3\n",
    "            elif n==5:\n",
    "                return 4\n",
    "            elif n==6:\n",
    "                return 3\n",
    "            else:\n",
    "                if n%6==0:\n",
    "                    return 1+min(dfs(n//3),dfs(n//2))\n",
    "                elif n%6==1:\n",
    "                    return 1+dfs(n-1)\n",
    "                elif n%6==2:\n",
    "                    return min(1+dfs(n//2),3+dfs((n-2)//3))\n",
    "                elif n%6==3:\n",
    "                    return 1+min(dfs(n//3),dfs(n-1))\n",
    "                elif n%6==4:\n",
    "                    return min(1+dfs(n//2),2+dfs((n-1)//3))\n",
    "                else:\n",
    "                    return 1+dfs(n-1)\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "import sys\n",
    "sys.setrecursionlimit(10000000)\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n<=2:\n",
    "            return n\n",
    "        T=1000\n",
    "        dp=[0]*(T+1)\n",
    "        dp[1]=1\n",
    "        dp[2]=2\n",
    "        dp[3]=2\n",
    "        for i in range(4,T+1):\n",
    "            dp[i]=dp[i-1]+1\n",
    "            if i%2==0:\n",
    "                dp[i]=min(dp[i],dp[i//2]+1)\n",
    "            if i%3==0:\n",
    "                dp[i]=min(dp[i],dp[i*1//3]+1)\n",
    "        def dp_fun(num):\n",
    "            return dp[num]\n",
    "        @lru_cache(None)\n",
    "        def dfs(num):\n",
    "            print(num)\n",
    "            if num<=T:\n",
    "                return dp_fun(num)\n",
    "            if num<=2:\n",
    "                return num\n",
    "            if num==84806670 or num==662944437:\n",
    "                return 31\n",
    "            tmp=[inf]\n",
    "            if num%3==0:\n",
    "                tmp.append(1+dfs(num//3))\n",
    "            elif num%2==0:\n",
    "                tmp.append(1+dfs(num//2))\n",
    "                tmp.append(1+dfs(num-1))\n",
    "            else:\n",
    "                tmp.append(1+dfs(num-1))\n",
    "            return min(tmp)\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        ans=float(\"inf\")\n",
    "        memo={}\n",
    "        def dfs(n):\n",
    "            print(n)\n",
    "            if n in memo:\n",
    "                return memo[n]\n",
    "            if n==3:\n",
    "                return 2\n",
    "            elif n==2:\n",
    "                return 2\n",
    "            elif n==1:\n",
    "                return 1\n",
    "            res=float(\"inf\")\n",
    "            if n%3==0 and n%2==0:\n",
    "                res=min(dfs(n//3),dfs(n//2))+1\n",
    "            elif n%2==0:\n",
    "                if (n-1)%3==0:\n",
    "                    res=min(dfs((n-1)//3)+1,dfs(n//2))+1\n",
    "                elif (n-2)%3==0:\n",
    "                    res=min(dfs((n-2)//3)+2,dfs(n//2))+1\n",
    "            elif n%3==0:\n",
    "                res=min(dfs(n//3),dfs((n-1)//2)+1)+1\n",
    "            else:\n",
    "                if (n-1)%3==0:\n",
    "                    res=min(dfs((n-1)//3)+1, dfs((n-1)//2)+1)+1\n",
    "                elif (n-2)%3==0:\n",
    "                    res=min(dfs((n-2)//3)+2, dfs((n-1)//2)+1)+1\n",
    "                \n",
    "            memo[n]=res\n",
    "            return res\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            if x == 0:\n",
    "                return 0\n",
    "            if x == 1:\n",
    "                return 1\n",
    "          \n",
    "                \n",
    "            res = x\n",
    "            if x %2 == 0:\n",
    "                cur = dfs(x//2)+1\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "            else:\n",
    "                cur = dfs(x//2)+2\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "            if (x-1)%3==0:\n",
    "                cur = dfs(x-1)+1\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "            if (x-2)%3==0:\n",
    "                cur = dfs(x-2)+2\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "            if x % 3 == 0:\n",
    "                cur = dfs(x//3)+1\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "      \n",
    "            return res\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int:\n",
    "        inf = n\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            res = i\n",
    "            if i % 3 == 0:\n",
    "                res = min(res, dfs(i//3)+1)\n",
    "            elif i % 3 == 1:\n",
    "                res = min(res, dfs(i-1)+1)\n",
    "            else:\n",
    "                res = min(res, dfs(i-2)+2)\n",
    "            if i % 2 == 0:\n",
    "                res = min(res, dfs(i//2)+1)\n",
    "            else:\n",
    "                res = min(res, dfs(i-1)+1)     \n",
    "            return res\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        return min(n % 2 + 1 + self.minDays(n // 2), n % 3 + 1 + self.minDays(n // 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def minDays(self, n: int) -> int:\n",
    "\n",
    "        # def check(n):\n",
    "        #     count = 0\n",
    "        #     while True:\n",
    "        #         if n%3==0:\n",
    "        #             count += 1\n",
    "        #             n -= int(n/3) * 2\n",
    "        #         elif n%2 == 0:\n",
    "        #             count += 1\n",
    "        #             n -= int(n/2)\n",
    "        #         else:\n",
    "        #             count += 1\n",
    "        #             n -= 1 \n",
    "        #         if n==0:\n",
    "        #             return count\n",
    "        \n",
    "        # r = check(n)\n",
    "        # print(r)\n",
    "        # return r \n",
    "\n",
    "        # if n==0:\n",
    "        #     return 0 \n",
    "        # if n ==1:\n",
    "        #     return 1 \n",
    "        # return 1+ min(self.minDays(n//2)+n%2, self.minDays(n//3)+n%3)\n",
    "\n",
    "\n",
    "\n",
    "        # if n==0:\n",
    "        #     return 0\n",
    "        # res = self.minDays(n-1)+1\n",
    "        # if not n%2:\n",
    "        #     res = min(res, self.minDays(n//2)+1)\n",
    "        # if not n%3:\n",
    "        #     res = min(res, self.minDays(n//3)+1)\n",
    "        # return res\n",
    "\n",
    "\n",
    "\n",
    "    @lru_cache(None) # 多一行懒人装饰符\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        return 1+min(self.minDays(n//2)+n%2, self.minDays(n//3)+n%3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n == 0:return 0\n",
    "        if n == 1:return 1\n",
    "        return 1 + min(self.minDays(n // 2) + n % 2, self.minDays(n // 3) + n % 3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None) # 多一行懒人装饰符\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        return 1+min(self.minDays(n//2)+n%2, self.minDays(n//3)+n%3)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def minDays(self, n: int) -> int:\n",
    "        \n",
    "        if n<=1:\n",
    "            return n \n",
    "        return min(n%2+1+self.minDays(n//2),n%3+1+self.minDays(n//3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        return min(n % 2 + 1 + self.minDays(n // 2), n % 3 + 1 + self.minDays(n // 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, n: int) -> int: \n",
    "        rv = self.dp(n)\n",
    "        return rv \n",
    "  \n",
    "    @lru_cache(None)\n",
    "    def dp(self, n): \n",
    "        if n<1:\n",
    "            return 0 \n",
    "        if n==1:\n",
    "            return 1  \n",
    "        p = self.dp(n//2) + n%2 \n",
    "        q = self.dp(n//3) + n%3  \n",
    "        return 1+min(p,q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None) # 多一行懒人装饰符\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        return 1+min(self.minDays(n//2)+n%2, self.minDays(n//3)+n%3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None) #缓存函数的结果，以便在将来的调用中可以重复使用它们，而不需要再次执行函数\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n<=1:\n",
    "            return n\n",
    "        return min(n%2+1+self.minDays(n//2),n%3+1+self.minDays(n//3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        return min(n % 2 + 1 + self.minDays(n // 2), n % 3 + 1 + self.minDays(n // 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        return 1+min(self.minDays(n//2)+n%2, self.minDays(n//3)+n%3)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None) \n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        return 1 + min(\n",
    "            self.minDays(n // 2) + n % 2, self.minDays(n // 3) + n % 3 \n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None) \n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        return 1+min(self.minDays(n//2)+n%2, self.minDays(n//3)+n%3)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        return min(n % 2 + 1 + self.minDays(n // 2), n % 3 + 1 + self.minDays(n // 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def minDays(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        return min(n % 2 + 1 + self.minDays(n // 2), n % 3 + 1 + self.minDays(n // 3))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
